package tree

/*
	二叉树的遍历方法：
	1.递归 时间复杂度O(n),空间复杂度O(n)
    2.栈迭代 时间复杂度O(n),空间复杂度O(n),栈是一种 先进后出的结构，
    3.Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)O(1)，用递归和迭代的方式都使用了辅助的空间，而莫里斯遍历的优点是没有使用任何辅助空间。
	缺点是改变了整个树的结构，强行把一棵二叉树改成一段链表结构
    4.颜色标记法：以中序遍历为例：
		（1）使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色
		（2）如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈（注意：中序遍历的入栈顺序）
        （3）如果遇到的节点为灰色，则将节点的值输出。（注意：中序遍历的出栈顺序）
*/

type Pair struct {
	*Node
	flag int
}

func InorderIterationColoring(root *Node) (order []int) {
	if root == nil {
		return
	}

	stack := make([]Pair, 0)
	stack = append(stack, Pair{root, 0}) // 0:white indicates unvisited
	for len(stack) > 0 {
		pair := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if pair.Node == nil {
			continue
		}
		switch pair.flag {
		case 0:
			stack = append(stack, Pair{pair.Right, 0})
			stack = append(stack, Pair{pair.Node, 1})
			stack = append(stack, Pair{pair.Left, 0})
		case 1:
			order = append(order, pair.Val)
		}
	}
	return
}

func MorrisPreorderTraversal(root *Node) (vals []int) {
	var p1, p2 *Node = root, nil
	for p1 != nil {
		p2 = p1.Left
		if p2 != nil {
			for p2.Right != nil && p2.Right != p1 {
				p2 = p2.Right
			}
			if p2.Right == nil {
				vals = append(vals, p1.Val)
				p2.Right = p1
				p1 = p1.Left
				continue
			}
			p2.Right = nil
		} else {
			vals = append(vals, p1.Val)
		}
		p1 = p1.Right
	}
	return
}

func morrisReverse(a []int) {
	for i, n := 0, len(a); i < n/2; i++ {
		a[i], a[n-1-i] = a[n-1-i], a[i]
	}
}

func MorrisPostorderTraversal(root *Node) (res []int) {
	addPath := func(node *Node) {
		resSize := len(res)
		for ; node != nil; node = node.Right {
			res = append(res, node.Val)
		}
		morrisReverse(res[resSize:])
	}

	p1 := root
	for p1 != nil {
		if p2 := p1.Left; p2 != nil {
			for p2.Right != nil && p2.Right != p1 {
				p2 = p2.Right
			}
			if p2.Right == nil {
				p2.Right = p1
				p1 = p1.Left
				continue
			}
			p2.Right = nil
			addPath(p1.Left)
		}
		p1 = p1.Right
	}
	addPath(root)
	return
}

func MorrisInorderTraversal(root *Node) (res []int) {
	for root != nil {
		if root.Left != nil {
			// predecessor 节点表示当前root节点向左走一步，然后一直向右走至无法走为止的节点
			predecessor := root.Left
			for predecessor.Right != nil && predecessor.Right != root {
				//有右子树且没有设置过指向root,则继续向右走
				predecessor = predecessor.Right
			}
			if predecessor.Right == nil {
				//将 predecessor的右指针指向root,这样后面遍历完左子树root.Left后，就能通过这个指向回到root
				predecessor.Right = root //右边整体搬移
				root = root.Left
			} else { //predecessor 的右指针已经指向了root,则表示左子树root.Left已经访问问了
				res = append(res, root.Val)
				//恢复原样
				predecessor.Right = nil
				//遍历右子树
				root = root.Right
			}
		} else { //没有左子树
			res = append(res, root.Val)
			root = root.Right
		}
	}
	return
}

func InorderTraversalRecursion(root *Node) (res []int) {
	//利用闭包和函数变量
	var inorder func(node *Node)
	inorder = func(node *Node) {
		if node == nil {
			return
		}
		inorder(node.Left)
		res = append(res, node.Val)
		inorder(node.Right)
	}

	inorder(root)
	return
}

// 前序排序递归方式
func PreorderTraversalRecursion(root *Node) (res []int) {

	var preOrder func(node *Node)
	preOrder = func(node *Node) {
		if node == nil {
			return
		}

		res = append(res, node.Val)
		preOrder(node.Left)
		preOrder(node.Right)
	}

	preOrder(root)

	return

}

//前序排序 通过栈
func PreorderTraversalWithStack(root *Node) []int {
	if root == nil {
		return nil
	}

	result := make([]int, 0)
	stack := make([]*Node, 0)

	for root != nil || len(stack) > 0 {
		for root != nil {
			//前序遍历，先保存结果
			result = append(result, root.Val)
			//入栈
			stack = append(stack, root)
			root = root.Left
		}

		//pop
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		root = node.Right
	}
	return result
}

func InorderTraversalWithStack(root *Node) []int {
	result := make([]int, 0)
	if root == nil {
		return result
	}
	stack := make([]*Node, 0)
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		//pop
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, node.Val)

		root = node.Right

	}
	return result
}

func PostorderTraversalWithStack(root *Node) []int {
	result := make([]int, 0)
	if root == nil {
		return result
	}
	stack := make([]*Node, 0)
	var lastVisit *Node
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		node := stack[len(stack)-1]

		// 根节点必须在右节点弹出之后，再弹出
		if node.Right == nil || node.Right == lastVisit {
			stack = stack[:len(stack)-1]
			result = append(result, node.Val)
			lastVisit = node
		} else {
			root = node.Right
		}

	}

	return result
}
